class Solution {
public:
    TreeNode* dfs(TreeNode* root,TreeNode* p,TreeNode*q){
        if(!root||root==p||root==q) return root; //若当前节点即要找的节点直接返回

        TreeNode* left=dfs(root->left,p,q); //找左子树
        TreeNode* right=dfs(root->right,p,q); //找右子树

        if(!left) return right; //若左子树没找到直接返回右
        if(!right) return left;

        return root; //若左右都能找到说明当前节点是最近祖先节点
    } 

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return dfs(root,p,q);
    }
};